package test.net.cloudsun.tree.rb;

import net.cloudsun.tree.rb.RBNode;
import net.cloudsun.tree.rb.RBTree;

import java.util.HashSet;
import java.util.concurrent.atomic.AtomicBoolean;
import java.util.concurrent.atomic.AtomicInteger;

/**
 * 红黑树校验工具
 *
 * @author Ryan
 * @since 1.2
 */
public class RBTreeErrorTestUtil {
    /**
     * 红黑树错误校验工具
     * @param tree 红黑树
     * @return 是否错误
     */
    public static boolean hasError(RBTree<Integer> tree) {
        AtomicBoolean error = new AtomicBoolean(false);
        final HashSet<Integer> blackCount = new HashSet<>();
        tree.dfs(x-> {
            final RBNode<Integer> rbNode = (RBNode<Integer>) x;
            if (rbNode.isEmpty()) {
                // 这是根节点
                AtomicInteger blacks = new AtomicInteger(0);
                rbNode.listParent(p-> {
                    if (((RBNode<Integer>)p).getColor() == RBNode.BLACK) {
                        blacks.incrementAndGet();
                    }
                });
                blackCount.add(blacks.intValue() + 1);
            } else if (rbNode.getChildren().size() == 1) {
                AtomicInteger blacks = new AtomicInteger(0);
                rbNode.listParent(p-> {
                    if (((RBNode<Integer>)p).getColor() == RBNode.BLACK) {
                        blacks.incrementAndGet();
                    }
                });
                blackCount.add(blacks.intValue() + 1);
            }
            if (rbNode.getColor() == RBNode.RED && rbNode.getParent() != null && rbNode.getParent().getColor() == RBNode.RED) {
                error.set(true);
            }
            return true;
        });
        if (blackCount.size() > 1) {
            return true;
        }
        if (error.get()) {
            return true;
        }
        return false;
    }
}
